Жадная раскраска графа
Раскраска графов Примеры и применение
Корректной раскраской графа в два цвета называется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют двудольными. Заметим, что если такая раскраска существует, и если зафиксировать цвет одной вершины, то все цвета всех достижимых из неё вершин определяются однозначно: пусть цвет этой вершины белый, тогда все её соседи будут иметь черный цвет, все вершины на расстоянии 2 будут иметь снова белый цвет, все вершины на расстоянии 3 снова черный, и так далее. Проверять граф на двудольность и выводить раскраску можно обходом в глубину.
В теории графов , раскраски графа является частным случаем маркировки графа ; это присвоение меток, традиционно называемых «цветами», элементам графа с учетом определенных ограничений. В простейшей форме это способ раскраски вершин графа таким образом, чтобы никакие две соседние вершины не были одного цвета; это называется раскраской вершин. Аналогичным образом , край окраски присваивает цвет каждому краю , так что никакие два смежных ребра не имеют одинаковый цвет, а лицо окраски о наличии планарного графа присваивает цвет каждой грани или области , так что никакие два лица , которые разделяют границей не имеют такого же цвета. Раскраска вершин обычно используется для введения задач раскраски графов, поскольку другие задачи раскраски могут быть преобразованы в экземпляр раскраски вершин. Например, окраска ребер графа - это просто окраска вершин его линейного графа , а окраска граней плоского графа - это просто окраска вершин его двойственного графа.
При исследовании раскраски графа задач в математике и информатика , жадная раскраска или последовательная раскраска - это раскраска вершин графа , образованного жадный алгоритм , который последовательно рассматривает вершины графа и присваивает каждой вершине свой первый доступный цвет. Жадные раскраски можно найти за линейное время, но они, как правило, не используют минимально возможное количество цветов. Различный выбор последовательности вершин обычно приводит к разным раскраскам данного графа, поэтому большая часть исследований жадных раскрасок посвящена поиску хорошего упорядочения. Всегда существует порядок, который дает оптимальную раскраску, но, хотя такие порядки можно найти для многих специальных классов графов, их трудно найти в целом.
